def fibonacci_dp(n):
    """
    使用动态规划求解斐波那契数列
    """
    if n <= 1:
        return n

    # 创建dp数组，dp[i]表示第i个斐波那契数
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    # 填充dp数组
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 测试斐波那契
print("斐波那契数列测试:")
for i in range(10):
    print(f"F({i}) = {fibonacci_dp(i)}")


# 空间优化版本
def fibonacci_optimized(n):

    if n <= 1:
        return n

    prev2, prev1 = 0, 1

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1


print(f"\n空间优化版本: F(10) = {fibonacci_optimized(10)}")